package com.zwx.linkList.leetcode_1;

import com.fasterxml.jackson.databind.util.LinkedNode;

import java.util.LinkedList;

/**
 * 回文链表
 * 判断一个链表是否为回文链表
 * <p>
 * 输入: 1->2
 * 输出: false
 * <p>
 * 输入: 1->2->2->1
 * 输出: true
 *
 * @author 文希
 * @create 2019-07-02 22:22
 */
public class PalindromesLinkList {

    /**
     * 设置快慢两个指针遍历链表，并逆序记录前半段节点的值，与后半段节点顺次对比。
     */
    private static boolean isPalindromes(ListNode head) {
        if (head == null || head.next == null)
            return true;
        LinkedList<Integer> preList = new LinkedList<>();
        ListNode slow = head;
        ListNode fast = head;
        preList.add(slow.val); // 防止list集合为空，在这之前已做判空的操作了
        // 快慢指针，遍历到中点位置，逆序记录前半段节点值
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            preList.add(0, slow.val);
        }
        if (fast.next != null) {
            slow = slow.next;
        }
        for (int i = 0; slow != null; i++, slow = slow.next) {
            if (preList.get(i) != slow.val) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(1,null);
        ListNode listNode4 = new ListNode(2,listNode5);
        ListNode listNode3 = new ListNode(2,listNode4);
        ListNode listNode2 = new ListNode(2,listNode3);
        ListNode listNode1 = new ListNode(1,listNode2);

        boolean b = isPalindromes(listNode1);
        System.out.println("b = " + b);


    }
    /**
     * 定义链表的对象模型
     */
    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode() {

        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
